#include <bits/stdc++.h>

using namespace std;

/*
3085. 成为 K 特殊字符串需要删除的最少字符数
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个字符串 word 和一个整数 k。

如果 |freq(word[i]) - freq(word[j])| <= k 对于字符串中所有下标 i 和 j  都成立，则认为 word 是 k 特殊字符串。

此处，freq(x) 表示字符 x 在 word 中的出现频率，而 |y| 表示 y 的绝对值。

返回使 word 成为 k 特殊字符串 需要删除的字符的最小数量。

 

示例 1：

输入：word = "aabcaba", k = 0

输出：3

解释：可以删除 2 个 "a" 和 1 个 "c" 使 word 成为 0 特殊字符串。word 变为 "baba"，此时 freq('a') == freq('b') == 2。

示例 2：

输入：word = "dabdcbdcdcd", k = 2

输出：2

解释：可以删除 1 个 "a" 和 1 个 "d" 使 word 成为 2 特殊字符串。word 变为 "bdcbdcdcd"，此时 freq('b') == 2，freq('c') == 3，freq('d') == 4。

示例 3：

输入：word = "aaabaaa", k = 2

输出：1

解释：可以删除 1 个 "b" 使 word 成为 2特殊字符串。因此，word 变为 "aaaaaa"，此时每个字母的频率都是 6。

 

提示：

1 <= word.length <= 105
0 <= k <= 105
word 仅由小写英文字母组成。
*/

// 法一
class Solution {
public:
    int minimumDeletions(string word, int k) {
        // 字符出现频率
        unordered_map<char, int> freq_map;
        for (char ch : word)    freq_map[ch]++;

        // 进数组 然后排列
        vector<int> freqs;
        for (auto& pair : freq_map) freqs.push_back(pair.second);
        sort(freqs.begin(), freqs.end());

        // 最小删除次数 --> max
        int minDel = INT_MAX;
        int n = freqs.size();
        // 遍历所有可能的基准频率
        for (int i = 0; i < n; i++) {
            int f = freqs[i];         // 当前基准频率
            int upper = f + k;        // 允许的最大频率
            int deletions = 0;        // 当前基准下需要删除的总次数
            // 计算每个字符频率与基准频率的差值
            for (int cnt : freqs) {
                // 如果频率小于基准频率，需要全部删除
                if (cnt < f) deletions += cnt;  
                // 如果频率超过允许的最大频率，需要删除超出部分
                else if (cnt > upper)  deletions += cnt - upper;                   
                // 频率在[f, upper]范围内不需要删除
            }
            // 更新最小删除次数
            minDel = min(minDel, deletions);
        }

        // 额外情况 f = max_freq - k
        if (!freqs.empty()) {
            int max_freq = freqs.back();  // 最大频率
            int f = max(0, max_freq - k); // 计算基准频率
            int upper = f + k;
            int deletions = 0;
            
            // 同上计算删除次数
            for (int cnt : freqs) {
                if (cnt < f)  deletions += cnt;
                else if (cnt > upper)  deletions += cnt - upper;
            }
            minDel = min(minDel, deletions);
        }
        
        return minDel;  // 返回最小删除次数
    }
};

// 法二
/* 核心算法：寻找最大保留字符数
* 1. 遍历每个频率作为基准频率f
* 2. 计算以f为基准时能保留的最大字符数（f ≤ 保留频率 ≤ f+k）
* 3. 通过max_save记录所有基准频率中的最优解
*/
class Solution {
public:
    int minimumDeletions(string word, int k) {
        // 统计每个字母的出现频率（ASCII码转换）
        int n = word.size();
        int cnt[26]{}; // 初始化26个字母的计数器为0
        for (char c : word) {
            cnt[c - 'a']++; // 将字符映射到0-25的索引
        }

        // 对频率进行排序（升序），方便后续处理
        ranges::sort(cnt); // C++20的ranges库更安全的排序方式

        
        int max_save = 0; // 初始化最大保留字符数
        for (int i = 0; i < 26; i++) {
            // 跳过未出现的字母（频率为0）
            if (cnt[i] == 0) continue;

            int sum = 0; // 当前基准下的保留字符总数
            for (int j = i; j < 26; j++) {
                /* 调整策略：
                 * - 频率低于f+k的保留原值
                 * - 超过f+k的截断到f+k
                 * 这样保证所有频率差不超过k
                 */
                sum += min(cnt[j], cnt[i] + k);
            }
            max_save = max(max_save, sum); // 更新全局最大值
        }

        // 总删除数 = 原长度 - 最大保留数
        return n - max_save;
    }
};

// 法三
/* 核心算法：贪心策略寻找最小删除数
* 遍历每个频率v[i]作为基准，计算：
* - 保留v[i]到v[i]+k范围内的频率
* - 删除超出部分(v[j] > v[i]+k时删至v[i]+k)
* - 累计删除更小频率(v[0..i-1])的总数
*/

// 贪心就是zhui diao的

class Solution {
public:
    int minimumDeletions(string word, int k) {
        // 1. 统计每个字母的频率（ASCII码转换）
        int count[26] = {0}; // 初始化26个字母的计数器
        for (char w : word) {
            ++count[w - 'a']; // 字符映射到0-25的索引
        }

        // 2. 提取非零频率并排序（升序）
        vector<int> v;
        for (int i =  0; i < 26; ++i) {
            if (count[i] > 0) {
                v.push_back(count[i]);
            }
        }
        sort(v.begin(), v.end()); // 排序便于后续处理

        int res = word.size(); // 初始化结果为字符串总长度（全删）
        int acc = 0; // 累计已删除的小频率字母数

        for (int i = 0; i < v.size(); ++i) {
            // 剪枝：如果累计删除数已超过当前最优解，提前退出
            if (acc > res) break;

            int tmp = 0; // 当前基准下需要删除的字符数
            for (int j = i + 1; j < v.size(); ++j) {
                // 处理超出允许范围的频率（v[i]+k为上限）
                if (v[j] > k + v[i]) {
                    tmp += v[j] - k - v[i]; // 计算超出部分
                }
            }
            // 更新全局最优解：当前删除数 + 之前累计的小频率删除数
            res = min(res, tmp + acc);
            acc += v[i]; // 累计较小频率（后续基准不再考虑v[i]）
        }
        return res;
    }
};